package KnapsackP;

import java.util.Scanner;

public class Main {

	//动态规划算法 解决01背包问题
	
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();//物品的个数
		int m=sc.nextInt();//背包的容量
		int[] w=new int[n];//物品的重量
		int[] val=new int[n];
		for(int i=0;i<n;i++){
			w[i]=sc.nextInt();
			val[i]=sc.nextInt();
		}	
	
		
		//创建二维数组
		//v[i][j] 表示在前i个物品中能够装入到背包中的最大价值
		int[][] v=new int[n+1][m+1];
		
		//为了记录放入商品的情况
	    //定义一个二维数组
		int[][] path=new int[n+1][m+1];

		//初始化第一行和第一列 这里在本程序中 可以不去处理 因为默认为0
		for(int i=0;i<v.length;i++){
			v[i][0]=0;//把第一列设置为0
		}
		for(int i=0;i<v[0].length;i++){
			v[0][i]=0;//把第一行设置为0
		}
		
		//根据前面的公式 来进行动态规划处理
		for(int i=1;i<v.length;i++){//不处理第一行 因为全为0 i从1开始
			for(int j=1;j<v[0].length;j++){//代表不处理第一列 因为全为0  j从1开始
				//公式
				if(w[i-1]>j){//因为i从1开始 因此需要i-1
					v[i][j]=v[i-1][j];
				}else{//当w[i-1]<j
					//说明：
					//因为程序中的i从1开始，因此公示需要i-1
					//v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
					//因为需要记录商品存在在背包的情况 不能直接的使用价值比较公式
					//需要使用 if else 体现这个公示
					if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){
						v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
						//把当前记录在path
						path[i][j]=1;
					}else{
						v[i][j]=v[i-1][j];
					}
				}
			}
		}
		

		int sum=0;
		int i=path.length-1;//行的最大下标
		int j=path[0].length-1;//列的最大下标
		while(i>0 && j>0){//逆向遍历 从path数组的最后开始找
			if(path[i][j]==1){
				sum=sum+val[i-1];
				j -= w[i-1];
			}
			i--;
		}
		System.out.println(sum);

	}

}
